package cn.antblog.ruankao.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName NQueens2
 * @Description n皇后  csdn https://blog.csdn.net/qq_51133939/article/details/124808655
 * @Author YangJingyi
 * @Date 2023/9/22 9:12
 * @Version 1.0
 */
public class NQueens2 {
    /**
     * 首先，N皇后问题的回溯代码大致可以分为调用函数（这里就不使用java方法的概念了，感觉函数更顺口一点）、回溯算法、判断选择三个方法。
     * 调用函数:
     *  顾名思义，调用函数就是调用回溯算法解决问题的函数，该函数篇幅很短，主要用于定义路径、调用回溯函数、返回结果三个作用。
     */

     /*
        输入：n = 4
        输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
        解释：如上图所示，4 皇后问题存在两个不同的解法。
     */

    //res表示result，保存最后的结果
    List<List<String>> res = new ArrayList<>();

    /**
     * 调用函数
     * @param n  N 棋盘  N * N
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        //记录正确的结果
        ArrayList<StringBuilder> track = new ArrayList<>();
        //回溯算法
        backtrack(n, 0, track);
        //返回结果
        return res;
    }
    /*
        解释两点：
            返回类型为List<List<String>>，是因为返回值是一个集合，集合中的每个元素都是一种正确的解法，而每一种解法都是一个List<String>类型，如：
            [“.Q…”,“…Q”,“Q…”,“…Q.”]，这就是一个棋盘，一个正确的结果。
            记录正确的结果时，我使用了List<StringBuilder>而不是List<String>，是因为将 ‘.’ 修改为 ‘Q’ 时，StringBuilder 更简单一点。
     */

    /**
     * 回溯算法
     * @param n		   N皇后问题的 N
     * @param row       n*n 棋盘上的第几行
     * @param track     路径（结果）
     */
    public void backtrack(int n, int row, List<StringBuilder> track) {
        /*
            这是回溯算法必须要有的，如果没有条件，那么回溯算法将会一直递归；n皇后问题的条件是：
            当 n * n 大的棋盘上放置了 n 个皇后时，这种情况正确，递归结束并加入最终结果中。
            （chg函数是将 List<StringBuilder> 类型转换为 List<String> 类型）
         */
        //触发结束条件
        if(track.size() == n) {
            List<String> list = chg(track);
            res.add(list);
            return;
        }
        //sb 是棋盘中的某一行。
        StringBuilder sb = new StringBuilder();
        //进行初始化（“.”表示没有放棋子）
        for(int i = 0;i < n;i++) {
            sb.append(".");
        }
        //从第 0 列开始，第 n 列结束
        for(int i = 0;i < n;i++) {
            //排除不合法的选择
            if(!isValid(n, track, row, i)) {
                continue;
            }
            //尝试（尝试将第 row 行的第 i 列放置皇后）
            sb.setCharAt(i, 'Q');
            track.add(sb);
            //进入下一层决策树（进入下一行继续尝试）
            backtrack(n, row + 1, track);
            //取消选择（将皇后取消，并删除该行）
            sb.setCharAt(i, '.');
            track.remove(track.size() - 1);
        }
    }

    /**
     * 判断选择
     * @param n   N 皇后
     * @param track  记录路径 每一行路径
     * @param row  第几行
     * @param col 第几列
     * @return
     */
    public static boolean isValid(int n, List<StringBuilder> track, int row, int col) {
        //检查列中是否有皇后互相冲突
        for(int i = 0;i < row;i++) {
            //如果上方有‘Q’，不能放置，返回结果false。
            if(track.get(i).charAt(col) == 'Q') {
                return false;
            }
        }
        //检查 45度角是否有皇后
        // row -1 上一行
        // col + 1 后一列
        // i>=0 j<n 不超过边界，
        // i-- 往上查找  j++ 往右边 查找  总结： 右上方45°角方向角查找
        for(int i = row - 1, j = col + 1;i >= 0 && j < n;i--, j++) {
            if(track.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col - 1;i >= 0 && j >= 0;i--, j--) {
            if(track.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        return true;
    }

    //将 List<StringBuilder> 转换为 List<String>，可能多此一举，看看就好
    public static List<String> chg(List<StringBuilder> track) {
        List<String> list = new ArrayList<>();
        for(int i = 0;i < track.size();i++) {
            list.add(new String(track.get(i)));
        }
        return list;
    }

    public static void main(String[] args) {
        List<List<String>> lists = new NQueens2().solveNQueens(4);
        System.out.println(lists.toString());
    }

    /*
        public static void backtrack(int n, List<StringBuilder> track) {
            //触发结束条件（结束递归）
            if(......) {
                //向结果中添加一种解决方案
                res.add(list);
                //返回
                return;
            }

            for(int i = 0;i < n;i++) {
                //排除不合法的选择
                if(...) {
                    continue;
                }

                //做选择

                track.add(...);

                //进入下一层决策树
                backtrack(n, track);

                //取消选择
                track.remove(track.size() - 1);
            }

        }

     */

}
